package com.xiyou.week04.binaryReactor;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName：MergeKLists
 * @Author：西柚
 * @Date：2022/1/22 10:42 上午
 * @Versiion：1.0
 */
public class MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        Queue<Node> q = new LinkedList<Node>();
        for (ListNode listNode : lists) {
            if (listNode == null) {
                continue;
            }
            q.add(new Node(listNode.val, listNode));
        }
        ListNode head = new ListNode();
        ListNode tail = head;
        while (!q.isEmpty()) {
            Node node = q.poll();
            tail.next = node.listNode;
            tail = tail.next;
            ListNode next = node.listNode.next;
            if (next != null) {
                q.add(new Node(next.val, next));
            }
        }
        return head.next;
    }

    public class Node {
        int key;
        ListNode listNode;

        Node(int key, ListNode listNode) {
            this.key = key;
            this.listNode = listNode;
        }
    }

    // queue是大根堆
    // 需要用小根堆，我们可以反着重载小于号（定义为大于），欺骗库
    // Node(2,x) Node(3,y) Node(5,z)
    private boolean operator(Node a, Node b) {
        return a.key > b.key;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
